package com.yun.algorithmproblem.leetcode;

import java.util.HashMap;
import java.util.Map;

public class Leetcode460 {
    static class LFUCache {
        private static class Node {
            Node prev;
            Node next;
            int key;
            int value;
            int count;

            public Node() {
            }

            public Node(int key, int value, int count) {
                this.key = key;
                this.value = value;
                this.count = count;
            }
        }

        private static class DoublyLinkedList {
            Node head;
            Node tail;

            public DoublyLinkedList() {
                head = tail = new Node();
                head.next = tail;
                tail.prev = head;
            }

            public void addFirst(Node node) {
                Node oldFirst = head.next;
                head.next = node;
                node.prev = head;
                node.next = oldFirst;
                oldFirst.prev = node;
            }

            public void remove(Node node) {
                Node prev = node.prev;
                Node next = node.next;
                prev.next = next;
                next.prev = prev;
            }

            public Node removeLast() {
                Node last = tail.prev;
                remove(last);
                return last;
            }
        }

        private static class HeadNode {
            HeadNode prev;
            HeadNode next;
            int count;

            int listSize;
            DoublyLinkedList list;

            public HeadNode() {
                list = new DoublyLinkedList();
            }

            public HeadNode(int count) {
                this.count = count;
                list = new DoublyLinkedList();
            }
        }

        private static class HeadDoublyLinkedList {
            HeadNode head;
            HeadNode tail;

            public HeadDoublyLinkedList() {
                head = tail = new HeadNode();
                head.next = tail;
                tail.prev = head;
            }

            public void addFirst(HeadNode headNode) {
                HeadNode oldFirst = head.next;
                head.next = headNode;
                headNode.prev = head;
                headNode.next = oldFirst;
                oldFirst.prev = headNode;
            }

            public void remove(HeadNode headNode) {
                HeadNode prev = headNode.prev;
                HeadNode next = headNode.next;
                prev.next = next;
                next.prev = prev;
            }

            public void add(HeadNode headNode) {
                HeadNode next = headNode.next;
                if (next == tail || headNode.count + 1 != next.count) {
                    HeadNode newHeadNode = new HeadNode(headNode.count + 1);
                    headNode.next = newHeadNode;
                    newHeadNode.prev = headNode;
                    newHeadNode.next = next;
                    next.prev = newHeadNode;
                }
            }
        }

        private int capacity;

        public LFUCache(int capacity) {
            this.capacity = capacity;
        }

        HashMap<Integer, HeadNode> headMap = new HashMap<>();
        HeadDoublyLinkedList headList = new HeadDoublyLinkedList();
        HashMap<Integer, Node> map = new HashMap<>();

        public int get(int key) {
            if (!map.containsKey(key)) {//判断是否存在,不存在返回-1
                return -1;
            }
            //得到存在键对应的节点
            Node node = map.get(key);
            //找到该节点所在链表的头节点,关键字为节点已使用次数
            HeadNode headNode = headMap.get(node.count);
            //节点已使用次数加1
            node.count++;
            //头节点存储的list中删除掉该节点
            headNode.list.remove(node);
            //头节点存储的list大小减1
            headNode.listSize--;
            //为headList增加节点,如果头节点的count+1的下个节点不存在则创建;
            headList.add(headNode);
            //此时头节点的下个节点的count等于头节点count+1
            HeadNode headNext = headNode.next;
            //在哈希表中加入该节点
            headMap.put(headNext.count, headNext);
            //加入对应节点
            headNext.list.addFirst(node);
            //下个节点的list大小加1
            headNext.listSize++;
            //如果头节点list不存在节点,则删除头节点所在的链表和哈希表
            if (headNode.listSize == 0) {
                headMap.remove(headNode.count);
                headList.remove(headNode);
            }
            return node.value;
        }

        public void put(int key, int value) {
            if (map.containsKey(key)) {
                Node node = map.get(key);
                node.value = value;
                get(key);
            } else {
                Node node = new Node(key, value, 1);
                map.put(key, node);
                HeadNode headFirst = headList.head.next;
                if (headFirst != headList.tail && headFirst.count == 1) {
                    headFirst.list.addFirst(node);
                    headFirst.listSize++;
                } else {
                    HeadNode newHeadNode = new HeadNode(1);
                    newHeadNode.list.addFirst(node);
                    newHeadNode.listSize++;
                    headList.addFirst(newHeadNode);
                    headMap.put(1, newHeadNode);
                }
                if (map.size() > capacity) {
                    Node removed = headFirst.list.removeLast();
                    headFirst.listSize--;
                    if (headFirst.listSize == 0) {
                        headList.remove(headFirst);
                    }
                    map.remove(removed.key);
                }
            }
        }
    }

    public static void main(String[] args) {
        LFUCache test = new LFUCache(5);
        test.put(1, 2);
        test.put(2,3);
        test.get(1);
        test.put(1,3);
        for (Map.Entry<Integer, LFUCache.Node> m : test.map.entrySet()) {
            System.out.print("[key:" + m.getKey() + ",value:" + m.getValue().value + ",count:" + m.getValue().count + "] ");
        }
        System.out.println();
        for (Map.Entry<Integer, LFUCache.HeadNode> m : test.headMap.entrySet()) {
            System.out.print("[keyCount:" + m.getKey() + ",size :" + m.getValue().listSize + ",count:" + m.getValue().count + "] ");
        }
        System.out.println();
        LFUCache.HeadNode next = test.headList.head.next;
        while (next != test.headList.tail) {
            System.out.print("[size:" + next.listSize + ",count:" + next.count + "] ");
            next = next.next;
        }
        System.out.println();
    }
}
